note: 虽然是简单题,但是挺麻烦,尤其是在(好久)没做过的情况下,建议记住方法二的第二种写法,更简洁易懂一点。
题目描述 输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1:
1 2 输入:matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出:[1,2,3,6,9,8,7,4,5]
示例 2:
1 2 输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出:[1,2,3,4,8,12,11,10,9,5,6,7]
限制:
1 2 0 <= matrix.length <= 100 0 <= matrix[i].length <= 100
方法一 模拟 思路 通过方向数组模拟遍历路径,以便进行顺时针旋转。同时搭配一个标识是否访问过的数组,防止重复访问。
首先是向右、向下、向左和向上的方向数组:
static constexpr int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向数组
使用方向索引directionIndex
来决定选用那个方向数组。
然后引入理论下标 nextRow
和nextColumn
,来计算方向不改变时,下一个要访问的元素的下标。
判断理论下标 是否合法,不合法的情况有两个,其一是数组越界,其二是访问的元素已经访问过了。
当理论下标不合法 时,变换方向索引到顺时针的下个方向。
然后更新下标为真实的合法下标。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution {private : static constexpr int directions[4 ][2 ] = {{0 , 1 }, {1 , 0 }, {0 , -1 }, {-1 , 0 }}; public : vector<int > spiralOrder (vector<vector<int >>& matrix) { if (matrix.size () == 0 || matrix[0 ].size () == 0 ) { return {}; } int rows = matrix.size (), columns = matrix[0 ].size (); vector<vector<bool >> visited (rows, vector<bool >(columns)); int total = rows * columns; vector<int > order (total) ; int row = 0 , column = 0 ; int directionIndex = 0 ; for (int i = 0 ; i < total; i++) { order[i] = matrix[row][column]; visited[row][column] = true ; int nextRow = row + directions[directionIndex][0 ], nextColumn = column + directions[directionIndex][1 ]; if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) { directionIndex = (directionIndex + 1 ) % 4 ; } row += directions[directionIndex][0 ]; column += directions[directionIndex][1 ]; } return order; } };
复杂度分析
时间复杂度$O(mn)$。要遍历所有的元素,m n分别为矩阵的长和宽
空间复杂度$O(mn)$。需要一个和矩阵相同大小的二维数组作为标记数组。
方法二 按层遍历 思路 方法一的思路是矩阵不变,标记已访问的元素避免重复访问。
事实上,我们也可以不断改变矩阵的边界,达到一层层缩小矩阵的边界的效果,按层遍历,从而可以得到顺时针遍历同样的效果。
我们用四个变量l r t b
代表当前层的矩阵的左右上下边界
在左边界大于右边界、上边界大于下边界之前,我们重复四个步骤
从左到右访问上边界那一排元素
从上到下访问右边界那一列元素
如果左上边界都小于右下边界,那么我们
从右到左访问下边界这一排元素
从下到上访问左边界这一排元素
更改边界,左边界上边界自增,右边界下边界自减。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution {public : vector<int > spiralOrder (vector<vector<int >>& matrix) { if (matrix.size ()==0 || matrix[0 ].size ()==0 ){ return {}; } int m = matrix.size (),n=matrix[0 ].size (); int l=0 ,r=n-1 ,t=0 ,b=m-1 ; vector<int > ans; while (l<=r && t<=b){ for (int i=l;i<=r;i++){ ans.push_back (matrix[t][i]); } for (int i=t+1 ;i<=b;i++){ ans.push_back (matrix[i][r]); } if (l < r && t < b){ for (int i=r-1 ;i>l;i--){ ans.push_back (matrix[b][i]); } for (int i=b;i>t;i--){ ans.push_back (matrix[i][l]); } } l++; r--; t++; b--; } return ans; } };
如果较难理解,还有一种写法,即在每排每列访问完后,立刻进行边界的缩小,并判断是否合法,如果不合法则说明已经遍历完毕,可以直接结束
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { if (matrix.empty()) return {}; vector<int> res; int l = 0; //左边界 int r = matrix[0].size() - 1; //右边界 int t = 0; //上边界 int b = matrix.size() - 1; //下边界 while (true) { //left -> right for (int i = l; i <= r; i++) res.push_back(matrix[t][i]); if (++t > b) break; //top -> bottom for (int i = t; i <= b; i++) res.push_back(matrix[i][r]); if (--r < l) break; //right -> left for (int i = r; i >= l; i--) res.push_back(matrix[b][i]); if (--b < t) break; //bottom -> top for (int i = b; i >= t; i--) res.push_back(matrix[i][l]); if (++l > r) break; } return res; } };
复杂度分析
时间复杂度:$O(mn)$。要访问矩阵种所有的元素
空间复杂度:$O(1)$。不需要标记数组。
原文链接: https://zijian.wang/2021/07/19/29. 顺时针打印矩阵/
版权声明: 转载请注明出处.